package test.example;

import com.bobo.data.DataStore;

import java.util.Arrays;

public class HeapSort {
    private static int len=10;
    public static void main(String[] args) {
        int data[]= DataStore.data;
        px(data);
        System.out.println("args = " + Arrays.toString(data));
    }

    public static void buildMaxHeap(int arr[]) {   // 建立大顶堆
        int len = arr.length;
        for (int i = len/2; i >= 0; i--) {
            heapify(arr, i);
        }
    }

    public static void heapify(int arr[],  int i) {     // 堆调整
        int left = 2 * i + 1,
                right = 2 * i + 2,
                largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest);
        }
        }

    public static void swap(int arr[],int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static int [] px(int arr[]) {
        buildMaxHeap(arr);

        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return arr;
    }

}
